static vector<vector<int>> nextP = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

class Solution {
public:

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& book, int x, int y) {

            book[x][y] = true;
            for (int i = 0; i < nextP.size(); i++) {
                int newX = x + nextP[i][0];
                int newY = y + nextP[i][1];
                if (newX < 0 || newX >= grid.size() || newY < 0 || newY >= grid[0].size()) continue;
                if (grid[newX][newY] == '1' && book[newX][newY] == false) {
                    dfs(grid, book, newX, newY);
                }
            }
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        int result = 0;


        vector<vector<bool>> book(m, vector<bool>(n, false)); 

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && book[i][j] == false) {
                    dfs(grid, book, i, j);
                    result++;
                }
            }
        }
        return result;
    }
};
